1. Field of the Invention
The present invention relates to a system for merge sorting, i.e., data sequencing by comparison of number size, using database processing hardware.
2. Description of the Related Art
Generally, a record that is an element of a database consists of a plurality of fields. The process of sequencing records in an ascending or descending order using a particular field as a key is referred to as sorting. The process of reorganizing a plurality of sorted record arrays into one sorted record array is referred to as merging.
When performing sorting or merging using software, as a large amount of data is transferred within a processor, a memory, and a supplementary memory device such as a disk, a great deal of processing time is required. In contrast, a hardware pipeline merge sorting device can be provided to perform sorting at a high speed.
FIG. 10 is a block diagram showing a configuration of a pipeline merge sorting device described, for example, in "VLSI Sort Processor" (Information Processing, Vol. 31, No.4, 1990). FIG. 10 includes linearly connected sort processors 1000, 1001, 1002, and 1003, and memory units 1010, 1011, 1012, and 1013 connected to respective sort processors.
In the pipeline merge sorting device, the n.sup.th sort processor receives from the n-1.sup.th sort processor an input of two sets of sorted record arrays each comprising 2.sup.n-1 records. The n.sup.th sort processor merges the two sets of record arrays and outputs one set of sorted record array comprising 2.sup.n records. The first record array of the two sets of record arrays is stored in the memory units connected to respective sort processors. The sorting process using the pipeline merge sorting device is shown in FIG. 11.
FIG. 11 illustrates an example of transitional changes a record array undergoes when processed by two-way merge sorting. Generally in K-way merge sorting, the n.sup.th sort processor receives from the n-1.sup.th sort processor an input of K sets of sorted record arrays each comprising K.sup.n-1 records. The n.sup.th sort processor merges the K sets of record arrays and outputs one set of sorted record array comprising K.sup.n records.
FIG. 12 is a diagram showing a configuration of a sort processor performing 8-way merge sorting using a tournament tree system. FIG. 12 includes comparison nodes 1100-1120, eight registers 1200-1207 retaining data to be introduced into the tournament circuit, and a register 1210 retaining data winning a comparison. Data from registers 1200 and 1201 are input to the comparison node 1100 corresponding to a first round match of the tournament. The output from this node 1100 serves as one of the two inputs to the comparison node 1110 corresponding to a second round match. As the other input to the node 1110, the output from the comparison node 1101 corresponding to a different first round match is received. The output from the node 1100 serves as one of the two inputs to the comparison node 1120 corresponding to the third round match, or the final round. The output from the node 1120 serves as the input to the register 1210.
FIG. 13 is a block diagram illustrating in greater detail a comparison node shown in FIG. 12. Both data X and data Y serve as inputs to the comparator 1500 and the selector 1510. Selection is performed in the selector 1510 in accordance with the comparison result from the comparator 1500. The selector 1510 then outputs data Z.
The operation performed in the configuration of FIGS. 12 and 13 will now be explained. A sorted record array, such as the one shown in FIG. 4, is input word by word to the input registers 1200-1207. Each of the records in a record array comprises a key and a main record portion. Initially, the first word of the key of each foremost record in record arrays 0-7 is set in each of the registers 1200-1207, and respective subsequent words are sequentially set in the registers as necessary.
However, in conventional 8-way merge sorting, eight record arrays must constantly be supplied to the input registers 1200-1207. Record arrays are generally stored in a common memory and read out via a common data path. As the eight record arrays constantly vie for readout, merge-sorting performance is degraded.
To prevent such performance degradation, Japanese Patent Laid-Open Publication No. Hei 4-247571 discloses a data processing apparatus with an improved exchange and selection system, wherein, for example, 16-way merge sorting is executed by constantly comparing five records. This execution process corresponds to executing 8-way merge sorting by comparison of four records.
The above art, however, requires processes for initializing the registers comprising the tournament tree, for which extra clock cycles are necessary. More specifically, in 8-way merge sorting, for example, an extra clock cycle is inserted after every eight records in the first sort processor of the pipeline merge sorting device. This insertion may lead to performance degradation of the entire pipeline merge sorting device.
As such, in conventional K-way merge sorting, there remains the problem of performance degradation due to either the contending readouts of record arrays from memory or the requirement of extra clock cycles for initializing the registers of the tournament tree.